package com.example.leetcode;

/**
 * 跳跃游戏2   动态规划  贪心算法
 * 最少跳跃次数 ** 参考题解 ** 难点
 */
public class Demo0045 {
    public static void main(String[] args) {
        int[] ints=new int[]{7,0,9,6,9,6,1,7,9,0,1,2,9,0,3};
        jump(ints);
    }

    public static int jump(int[] nums) {
        int len = nums.length;
        int right=0;
        int step=0;
        int end=0;
        for (int i = 0; i < len-1; i++) {
            right=Math.max(right,i+nums[i]);
            if (i==end){
                end=right;
                step++;
            }
        }
        return step;
    }

    public static int jump1(int[] nums){
        int len = nums.length;
        if (len==1){
            return 0;
        }
        int fun[] =new int[len];
        fun[0]=0;
        fun[1]=1;
        for (int i = 2; i < len; i++) {
            int min=Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                //如果j能达i;
                if (i<=nums[j]+j){
                    min=Math.min(fun[j]+1,min);
                }
            }
            fun[i]=min;
        }
        return fun[len-1];
    }

    /**
     *dp
     * 边界到0至少f(0)步 f(1) 到1至少f(1)步
     * f(i)  为 0-i之间至少的步数 再跨一步(并且可达)
     */
    public static int jump2(int[] nums){
        int len = nums.length;
        if (len==1){
            return 0;
        }
        int fun[] =new int[len];
        fun[0]=0;
        fun[1]=1;
        for (int i = 2; i < len; i++) {
            int min=Integer.MAX_VALUE;//初始化一个最小值做哨兵
            for (int j = 0; j < i; j++) {
                //如果j能跳到i
                if (j+nums[j]>=i){
                    min=Math.min(min,fun[j]+1);
                }
            }
            fun[i]=min;
        }
        return fun[len-1];
    }

    /**
     * 维护当前步数 与 当前可达最远距离 和下一步最远距离
     * 当i=当前最远时更新步数，更新当前步最远
     */
    public static int jump3(int[] nums){
        int len=nums.length;
        int step=0;
        int curStepRight =0;//当前步最右
        int nextStepRight=0;//下一步最右边
        for (int i = 0; i < len-1; i++) {
            //不断更新下一步最右边
            nextStepRight=Math.max(nextStepRight,nums[i]+i);
            //i等于了当前步最右则更新当前步数 以及当前步最右边  并且循环只需要更新到 倒数第二步 (已经遍历过curStepRight所有下一步最右了)
            if (i== curStepRight){
                step++;
                curStepRight=nextStepRight;
            }
        }
        return step;
    }
}
